package com.cheung.leetcode.greedy;

import org.junit.jupiter.api.Test;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.greedy
 * @Author :  cheungming
 * @CreateTime : 2024-06-04 08:28:28
 * @Description : 最大子序和
 * @Version : 1.0
 */
public class Code53Test {

    public int maxSubArray(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int num : nums) {
            cur += num;
            max = Math.max(max, cur);
            // 负数清零,但是不能和上面的代码交换顺序，否则会漏掉负数
            if (cur < 0) {
                cur = 0;
            }

        }
        return max;
    }

    @Test
    public void test1() {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        assert maxSubArray(nums) == 6;
    }

    @Test
    public void test2() {
        int[] nums = {1};
        assert maxSubArray(nums) == 1;
    }

    @Test
    public void test3() {
        int[] nums = {5, 4, -1, 7, 8};
        assert maxSubArray(nums) == 23;
    }
}
